﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace KQ.DCMMP.Common
{
    /// <summary>
    /// LD算法
    /// </summary>
    public static class LDUtility
    {
        /// <summary>
        /// str1或str2的长度为0返回另一个字符串的长度。
        ///初始化(n+1)*(m+1)的矩阵d，并让第一行和列的值从0开始增长。
        ///扫描两字符串（n*m级的），如果：str1[i] == str2[j]，用temp记录它，为0。否则temp记为1。
        ///然后在矩阵d[i][j]赋于d[i-1][j]+1 、d[i][j-1]+1、d[i-1][j-1]+temp三者的最小值。
        ///扫描完后，返回矩阵的最后一个值即d[n][m]
        ///最后返回的是它们的距离。怎么根据这个距离求出相似度呢？因为它们的最大距离就是两字符串长度的最大值。
        /// </summary>
        /// <param name="str1"></param>
        /// <param name="str2"></param>
        /// <returns></returns>
        private static int LD(String str1, String str2)
        {
            // 矩阵 
            int[][] d;
            int n = str1.Length;
            int m = str2.Length;
            // 遍历str1的 
            int i;
            // 遍历str2的 
            int j;

            // str1的 
            char ch1;
            // str2的 
            char ch2;
            // 记录相同字符,在某个矩阵位置值的增量,不是0就是1 
            int temp;
            if (n == 0)
            {
                return m;
            }
            if (m == 0)
            {
                return n;
            }
            d = new int[n + 1][];
            //m + 1
            for (int x = 0; x < d.Length; x++) { d[x] = new int[m + 1]; }
            for (i = 0; i <= n; i++)
            {
                // 初始化第一列 
                d[i][0] = i;
            }
            for (j = 0; j <= m; j++)
            {
                // 初始化第一行 
                d[0][j] = j;
            }
            for (i = 1; i <= n; i++)
            {
                // 遍历str1 
                ch1 = str1.Substring(i - 1, 1).ToCharArray()[0];
                // 去匹配str2 
                for (j = 1; j <= m; j++)
                {
                    ch2 = str2.Substring(j - 1, 1).ToCharArray()[0];
                    if (ch1 == ch2)
                    {
                        temp = 0;
                    }
                    else
                    {
                        temp = 1;
                    }
                    // 左边+1,上边+1, 左上角+temp取最小 
                    d[i][j] = Min(d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + temp);
                }
            }

            return d[n][m];
        }

        /// <summary>
        /// 计算两个字符串的相似度
        /// </summary>
        /// <param name="str1"></param>
        /// <param name="str2"></param>
        /// <returns></returns>
        public static double Sim(String str1, String str2)
        {
            if (null == str1 || null == str2)
            {
                return 0;
            }
            int ld = LD(str1, str2);
            return 1 - (double)ld / Math.Max(str1.Length, str2.Length);
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="one"></param>
        /// <param name="two"></param>
        /// <param name="three"></param>
        /// <returns></returns>
        private static int Min(int one, int two, int three)
        {
            int min = one;
            if (two < min)
            {
                min = two;
            }
            if (three < min)
            {
                min = three;
            }
            return min;
        }
    }
}
